package com.atguigui.leetcode1;

/**
 * P剑指Offer47.礼物的最大价值
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/3/8 9:11
 */
public class P剑指Offer47LiWuDeZuiDaJieZhiLcof {

    public static void main(String[] args) {
        Solution solution = new P剑指Offer47LiWuDeZuiDaJieZhiLcof().new Solution();
        // TO TEST
    }

    class Solution {
        public int maxValue(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int[][] f = new int[m][n];
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (i > 0) {
                        f[i][j] = Math.max(f[i][j], f[i - 1][j]);
                    }
                    if (j > 0) {
                        f[i][j] = Math.max(f[i][j], f[i][j - 1]);
                    }
                    f[i][j] += grid[i][j];
                }
            }
            return f[m - 1][n - 1];
        }
    }
}
